import java.util.*;

public class BinaryTree {
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    // 前序遍历
    void preOrder(TreeNode root) {
        if(root==null){
            return;
        }else {
            int ch = root.val;
            System.out.print(ch+" ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }
    // 中序遍历
    void inOrder(TreeNode root) {
        if(root==null){
            return;
        }else {
            int ch = root.val;
            preOrder(root.left);
            System.out.print(ch+" ");
            preOrder(root.right);
        }
    }
    // 后序遍历
    void postOrder(TreeNode root) {
        if(root==null){
            return;
        }else {
            int ch = root.val;
            preOrder(root.left);
            preOrder(root.right);
            System.out.print(ch+" ");
        }
    }

/*    public static int i=0;
    public static TreeNode createTree(String str){
        TreeNode root=null;
        if(str.charAt(i)!='#'){
            root=new TreeNode(str.charAt(i));
            i++;
            root.left=createTree(str);
            root.right=createTree(str);
        }else{
            i++;
        }
        return root;
    }*/
    // 获取树中节点的个数
    //只要节点不为空，那么就count++
    /*public  static  int count=0;
    public void size(TreeNode root) {
        if(root==null){
            return;
        }else{
            count++;
            size(root.left);
            size(root.right);
        }
    }*/

    //整棵树有多少个结点=左子树有多少个结点+右子树有多少个结点+1
    public int size(TreeNode root) {
        if(root==null){
            return 0;
        }
        return size(root.left)+size(root.right)+1;
    }

    // 获取叶子节点的个数
   /* public static int count=0;
    public void getLeafNodeCount(TreeNode root){
        if(root==null){
            return ;
        }
        if(root.left==null&&root.right==null){
            count++;
        }
        getLeafNodeCount(root.left);
         getLeafNodeCount(root.right);
    }*/


    public int getLeafNodeCount(TreeNode root){
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
    }
    // 子问题思路-求叶子结点个数
// 获取第K层节点的个数
    public int getKLevelNodeCount(TreeNode root,int k){
        if(root==null){
            return 0;
        }
        if(k==1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);

    }
    // 获取二叉树的高度
    public int getHeight(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);
        return Math.max(leftHeight,rightHeight)+1;
    }
    // 检测值为value的元素是否存在
    public TreeNode find(TreeNode root, int val){
        if(root==null){
            return null;
        }
        if(root.val==val){
            return root;
        }
        TreeNode leftNode=find(root.left,val);
        if(leftNode!=null){
            return leftNode;
        }
        TreeNode rightNode=find(root.right,val);
        if(rightNode!=null){
            return rightNode;
        }
        return null;
    }
    //层序遍历
    public void levelOrder(TreeNode root){
        List<List<Integer>> list=new ArrayList<>();
        if(root==null){
            return ;
        }
        TreeNode cur=root;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> list2=new ArrayList<>();
            int size=queue.size();
            while(size>0){
                cur=queue.poll();
                list2.add(cur.val);
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
                size--;
            }
            list.add(list2) ;
        }
    }
    // 判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root){
        if(root==null){
            return true;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        TreeNode cur=root;
        queue.offer(root);
        while(!queue.isEmpty()){
            cur=queue.poll();
            if(cur!=null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else{
                break;
            }
        }
        int size=queue.size();
        while(size>0){
            TreeNode now=queue.poll();
            if(now!=null){
                return false;
            }
            size--;
        }
        return true;

    }

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list=new LinkedList<>();
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top=stack.peek();
            if(top.right==null||list.contains(top.right.val)){
                top=stack.pop();
                list.add(top.val);
            }else{
                cur=top.right;
            }

        }
        return list;

    }
  /*  public boolean isSameTree(TreeNode p, TreeNode q) {
        //1.判断结构是否一样
        if((p!=null&&q==null)||(p==null&&q!=null)){
            return false;
        }
        //上述运行后通过的要么同为空，要么同不为空
        //同为空则正确
        if(p==null&&q==null){
            return true;
        }
        //2.判断值是否一样
        if(p.val!=q.val){
            return false;
        }
        //3.判断左子树，右子树是否一样
        return isSameTree(p.left, q.left)&&isSameTree(p.right, q.right);
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null){
            return false;
        }
        if(isSameTree(root, subRoot)){
            return true;
        }
        if(isSubtree(root.left, subRoot)){
            return true;
        }
        if(isSubtree(root.right, subRoot)){
            return true;
        }
        return false;
    }
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //1.判断结构是否一样
        if((p!=null&&q==null)||(p==null&&q!=null)){
            return false;
        }
        //上述运行后通过的要么同为空，要么同不为空
        //同为空则正确
        if(p==null&&q==null){
            return true;
        }
        //2.判断值是否一样
        if(p.val!=q.val){
            return false;
        }
        //3.判断左子树，右子树是否一样
        return isSameTree(p.left, q.left)&&isSameTree(p.right, q.right);
    }*/
    public TreeNode invertTree(TreeNode root) {
      if(root==null){
          return null;
      }
      TreeNode tmp=root.left;
      root.left=root.right;
      root.right=tmp;
      invertTree(root.left);
      invertTree(root.right);
      return root;


  }
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        int leftheight=getheight(root.left);
        int rightheight=getheight(root.right);
        return Math.abs(leftheight-rightheight)<2&&isBalanced(root.left)&&isBalanced(root.right);
     /*  if(Math.abs(leftheight-rightheight)>=2){
            return false;
        }
        if(isBalanced(root.left)&&isBalanced(root.right)){
            return true;
        }
        return false;*/
    }
    public int getheight(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftheight=getheight(root.left);
        int rightheight=getheight(root.right);
        return Math.max(leftheight,rightheight)+1;
    }
    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }
        return isSymmetricChild(root.left,root.right);

    }
    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){
        //判断结构一样
        if((leftTree==null&&rightTree!=null)||(leftTree!=null&&rightTree==null)){
            return false;
        }
        //左右同为空或者左右同不为空
        if(leftTree==null&&rightTree==null){
            return true;
        }
        if(leftTree.val!=rightTree.val){
            return false;
        }
        return isSymmetricChild(leftTree.left,rightTree.right)&&isSymmetricChild(leftTree.right,rightTree.left);

    }
    TreeNode prev = null;

    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null){
            return null;
        }
        ConvertChild(pRootOfTree);
        TreeNode head=pRootOfTree;
        while(head.left!=null){
            head=head.left;
        }
        return head;

    }
    public void ConvertChild(TreeNode root) {
        if (root == null) {
            return;
        }
        ConvertChild(root.left);
        root.left = prev;
        if (prev != null) {
            prev.right = root;
        }
        prev = root;
        ConvertChild(root.right);

    }
    public static int i=0;
    public static TreeNode createTree(String str){
        TreeNode root=null;
        if(str.charAt(i)!='#'){
            root=new TreeNode(str.charAt(i));
            i++;
            root.left=createTree(str);
            root.right=createTree(str);
        }else{
            i++;
        }
        return root;
    }
    public static void Inorder(TreeNode root){
        if(root==null){
            return;
        }
        Inorder(root.left);
        System.out.print(root.val+" ");
        Inorder(root.right);
    }

}
